perm filename TEST.TEX[TEX,DEK]1 blob sn#356211 filedate 1978-05-24 generic text, type C, neo UTF8
COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\input ACPhdr	 								% 1
C00019 ENDMK
C⊗;
\input ACPhdr	 								% 1
%Example TEX input related to Seminumerical Algorithms				% 2
\setcpage 1									% 3
\titlepage %This tells the page format routine not to put a page number on top 	% 4
\runninglefthead{RANDOM NUMBERS} \corners					% 5
\hjust{\def\\{\hskip 1pt}\:=C\\H\\A\\P\\T\\E\\R\hskip 10 pt T\\H\\R\\E\\E}	% 6
\vskip 1 cm plus 30 pt minus 10 pt						% 7
\rjustline{\:; RANDOM NUMBERS}							% 8
\vskip .5 cm plus 1 pc minus 5 pt						% 9
\quoteformat{Anyone who considers arithmetical\cr				%10
methods of producing random digits\cr is, of course,				%11
in a state of sin.\cr} author{JOHN VON NEUMANN (1951)}				%12
\quoteformat{Round numbers are always false.\cr}				%13
author{SAMUEL JOHNSON (c. 1750)}						%14
\vskip 1 cm plus 1 pc minus 5 pt						%15
\runningrighthead{INTRODUCTION} section{3.1}					%16
\sectionbegin{3.1.								%17
INTRODUCTION}									%18
Numbers which are ``chosen at random'' are useful in a wide variety of		%19
applications. For example:							%20
	% This blank line specifies end of paragraph				%21
\yskip	% This means a bit of extra space between paragraphs			%22
\textindent{a)}{\sl Simulation.}\xskip When a computer is used to simulate	%23
natural phenomena, random numbers are required to make things realistic.	%24
Simulation covers many fields, from the study of nuclear physics (where		%25
particles are subject to random collisions) to systems engineering (where	%26
people come into, say, a bank at random intervals).\par				%27
\yskip\textindent{b)}{\sl Sampling.}\xskip It is often impractical to examine	%28
all cases, but a random sample will provide insight into what constitutes	%29
``typical'' behavior.								%30
										%31
\yskip It is not easy to invent a foolproof random-number generator. This fact	%32
was convincingly impressed upon the author several years ago, when he attempted %33
to create a fantastically good random-number generator using the following	%34
peculiar method:								%35
										%36
\algbegin Algorithm K (``Super-random'' number					%37
generator). Given a 10-digit decimal number $X$, this algorithm may be		%38
used to change $X$ to the number which should come next in a supposedly random	%39
sequence.\par									%40
\algstep K1. [Choose number of iterations.] Set $Y←\lfloor X/10↑9 \rfloor$,	%41
i.e., the most significant digit of $X$. (We will execute steps K2 through K13,	%42
which cause $X$ to be transformed in various weird and wonderful ways,
$Y+1$ times; that is, we will randomize the digits a {\sl random} number of	%43
times.)\par									%44
\algstep K10. [99999 modify.] If $X<10↑5$, set $X←X↑2 + 99999$;			%45
otherwise set $X←X-99999$.\xskip\blackslug\par\yyskip				%46
										%47
\topinsert{\tablehead{Table 1}							%48
\def\fl{\hskip 0pt plus 1000cm minus 1000cm}
\hjust to size{\fl A COLOSSAL COINCIDENCE: THE NUMBER 6065038420\fl}		%49
\hjust to size{\fl IS TRANSFORMED INTO ITSELF BY ALGORITHM K.\fl}		%50
\vskip 4 pt \hrule								%51
\hjust to size{\fl\valign{\vskip 6pt#\vfill\vskip 6pt\cr			%52
\halign{\lft{#}\qquad⊗\ctr{#}⊗\qquad\lft{$#$}\cr				%53
Step⊗$X$ (after)\cr								%54
\noalign{\vskip 10 pt \vfill}							%55
K1⊗6065038420\cr K12⊗1905867781⊗Y=5\cr}	%end of \halign on line 53		%56
\cr					%end of first column to be \valigned	%57
\noalign{\qquad\vrule\qquad}		%vertical rule between columns		%58
\halign{\lft{#}\qquad⊗\ctr{#}⊗\qquad\lft{$#$}\cr				%59
Step⊗$X$ (after)\cr								%60
\noalign{\vskip 10 pt \vfill}							%61
K10⊗1620063735\cr								%62
K11⊗1620063735\cr K12⊗6065038420⊗Y=0\cr}%end of \halign on line 59		%63
\cr}\fl}				%end of 2nd \valigned column,\hjust     %64
\hrule}					%end of the \topinsert on line 48	%65
The moral to this story is that {\sl random numbers should not be 		%66
generated with a method chosen at random.} Some theory should be used.		%67
										%68
\exbegin{EXERCISES}								%69
\trexno 1. [20] Suppose that you wish to obtain a decimal digit at random, not  %70
using a computer. Shifting to exercise 16, let $f(x,y)$ be a function such that %71
if $0≤x,y<m$, then $0≤f(x,y)<m$. The sequence is constructed by selecting	%72
$X↓0$ and $X↓1$ arbitrarily, and then letting$$					%73
X↓{n+1} = f(X↓n,X↓{n-1}) \qquad \hjust{for} \qquad n>0.$$			%74
What is the maximum period conceivably attainable in this case?			%75
										%76
\exno 17. [10] Generalize the situation in the previous exercise so that	%77
$X↓{n+1}$ depends on the preceding $k$ values of the sequence.			%78
\par\vskip 0pt plus 100 cm\eject						%79
\runningrighthead{GENERATING UNIFORM RANDOM NUMBERS} section{3.2}		%80
\sectionbegin{3.2. GENERATING UNIFORM RANDOM NUMBERS}				%81
In this section we shall consider methods for generating a sequence of random	%82
fractions, i.e., random {\sl real numbers $U↓n$, uniformly distributed		%83
between zero and one.} Since a computer can represent a real number with only	%84
finite accuracy, we shall actually be generating integers $X↓n$ between		%85
zero and some number $m$; the fraction$$U↓n = X↓n/m \eqno(1)$$ will		%86
then lie between zero and one.							%87
										%88
\vskip.4in plus.2in minus.2in							%89
\runningrighthead{THE LINEAR CONGRUENTIAL METHOD} section{3.2.1}		%90
\sectionbegin{3.2.1. The Linear Congruential Method}				%91
By far the most successful random number generators known today are special	%92
cases of the following scheme, introduced by D. H. Lehmer in 1948. [See		%93
{\sl Annals Harvard Comp. Lab.} {\bf 26}(1951), 141-146.] We choose four	%94
``magic numbers'':$$								%95
\vcenter{\halign{\rt{$#$}⊗\lft{\quad#}⊗\quad\rt{$#$}⊗\lft{$\;#$}\cr		%96
X↓0,⊗the starting value;⊗X↓0⊗≥0.\cr						%97
m,⊗the modulus;⊗m⊗>X↓0,\quad m>a,\quad m>c.\cr}}\eqno(1)$$			%98
The desired sequence of random numbers $\langle X↓n \rangle$ is then		%99
obtained by setting$$X↓{n+1}=(aX↓n+c)\mod m,\qquad n≥0.\eqno(2)$$This is       %100
called a {\sl linear congruential sequence.}				       %101
									       %102
Let $w$ be the computer's word size. The following program computes $(aX+c)    %103
\mod(w+1)$ efficiently:$$\vcenter{\mixfour{				       %104
01⊗⊗LDAN⊗X⊗$\rA←-X.$\cr							       %105
02⊗⊗MUL⊗A⊗$\rAX ← (\rA)\cdot a.$\cr					       %106
03⊗⊗STX⊗TEMP\cr 05⊗⊗JANN⊗*+3⊗Exit if $\rA≥0.$\cr			       %107
07⊗⊗ADD⊗=$w$-1=⊗\qquad\blackslug\cr}}\eqno(2↑\prime)$$			       %108
\par\proofbegin    We have $x=1+qp↑e$ for some integer $q$ which is not a      %109
multiple of $p$. By the binomial formula$$				       %110
\eqalign{x↑p⊗=1+{p\choose 1}qp↑e+\cdots+{p\choose{p-1}}q↑{p-1}		       %111
p↑{(p-1)e}+q↑p p↑{pe}\cr						       %112
⊗=1+qp↑{e+1}\left(1+{1\over p}{p\choose 2}qp↑e + {1\over p}		       %113
{p\choose 3}q↑2 p↑{2e}+\cdots+{1\over p}{p\choose p}q↑{p-1}		       %114
p↑{(p-1)e}\right).\cr}$$ By repeated application of Lemma P, we find that      %115
$$\eqalign{(a↑{p↑g} - 1)/(a-1)⊗≡ 0 \modulo    				       %116
{p↑g},\cr(a↑{p↑g}-1)/(a-1)⊗\neqv 0 \modulo{p↑{g+1}}.\cr}\eqno(6)$$	       %117
If $1<k<p$, $p\choose k$ is divisible by $p$. \biglp{\sl Note:}\xskip A	       %118
generalization of this result appears in exercise 3.2.2-11(a).\bigrp\ By       %119
Euler's theorem (exercise 1.2.4-48), $a↑{\varphi(p↑{e-f})}≡ 1 \modulo	       %120
{p↑{e-f}}$; hence $λ$ is a divisor of$$					       %121
λ(p↓1↑{e↓1} \ldots p↓t↑{e↓t}) = \mathop{\hjust{\rm lcm}}\left(		       %122
λ(p↓1↑{e↓1},\ldots,λ(p↓t↑{e↓t})\right).\eqno(9)$$			       %123
									       %124
This algorithm in \MIX\ is simply$$					       %125
\vcenter{\mixtwo{							       %126
J6NN⊗*+2⊗\understep{A1. $j<0$?}\cr					       %127
STA⊗Z⊗\qquad$→Z$.\cr}}\eqno(7)$$					       %128
That was on page 26. If we skip to page 49, $Y↓1 +\cdots+ Y↓k$ will	       %129
equal $n$ with probability$$						       %130
\sum↓{\scriptstyle y↓1+\cdots+y↓k=n\atop\scriptstyle y↓1,\ldots,y↓k≥0}	       %131
\quad\prod↓{1≤s≤k}							       %132
{e↑{-np↓s}(np↓s)↑{y↓s}\over y↓s!}					       %133
={e↑{-n}n↑n\over n!}.$$							       %134
This is not hard to express in terms of $n$-dimensional integrals,$$	       %135
{{\int↓{α↓n}↑n \,dY↓n \int↓{α↓{n-1}}↑{Y↓n}				       %136
\,dY↓{n-1}\;\ldots\int↓{α↓1}↑{Y↓2}\,dY↓1}  \over		               %137
{\int↓0↑n \,dY↓n \int↓0↑{Y↓n} \,dY↓{n-1}\;\ldots			       %138
\int↓0↑{Y↓2}\,dY↓1}},\qquad\hjust{where}\qquad α↓j=			       %139
\max(j-t,0).\eqno(24)$$							       %140
This together with (25) implies that $$\def\rtn{\sqrt n}		       %141
\lim↓{n→∞} {s \over \rtn}						       %142
\sum↓{\rtn s<k≤n}{n\choose k}\left({k\over n} - {s\over \rtn}\right)↑k	       %143
\left({s\over\rtn} + 1 -{k \over n}\right)↑{n-k-1} = e↑{{-2s}↑2},\qquad s≥0,   %144
\eqno(27)$$ a limiting relationship which appears to be quite difficult to     %145
prove directly.								       %146
									       %147
\exbegin{EXERCISES---Special Set}\exno 17. [HM26] Let $t$ be a fixed real      %148
number. For $0≤k≤n$, let$$P↓{nk}(x)=\int↑x↓{n-t}\,dx↓n\int↓{n-1-t}↑{x↓n}\,     %149
dx↓{n-1}\;\,\ldots\int↓{k+1-t}↑{x↓{k+2}}\,dx↓{k+1}\int↓0↑{x↓{k+1}}	       %150
\,dx↓k\,\;\ldots\int↓0↑{x↓2}\,dx↓1;$$					       %151
another way to write these integrals, although I don't use it in my book, is
\def\jnt{\int\limitswitch}$$P↓{nk}(x)=\jnt↑x↓{n-t}\,dx↓n\jnt↓{n-1-t}↑{x↓n}\,   %149
dx↓{n-1}\;\,\ldots\jnt↓{k+1-t}↑{x↓{k+2}}\,dx↓{k+1}\jnt↓0↑{x↓{k+1}}	       %150
\,dx↓k\;\,\ldots\jnt↓0↑{x↓2}\,dx↓1.$$					       %151
Eq. (24)\footnote*{Page 68.} is equal to$$\def\sumk{\sum↓{1≤k≤n}}	       %152
\sumk X↑\prime↓k Y↑\prime↓k \left/\sqrt{\sumk{X↑\prime↓k}↑2}		       %153
\sqrt{\sumk{Y↑\prime↓k}↑2}\right..$$\par				       %154
\runningrighthead{A BIG MATRIX DISPLAY} section{3.3.3.3}		       %155
\subsectionbegin{3.3.3.3. This subsection doesn't exist}Finally, look at page  %156
91.$$\def\dgdts{\raise 6pt\hjust{.}\≥\raise 3pt\hjust{.}\≥.}		       %157
\def\5{\hskip5pt}
\eqalign{U⊗=\left(\vcenter{\halign{\ctr{$ #$}\quad⊗\ctr{$ #$}\quad⊗\ctr{$ #$}  %158
\quad⊗\ctr{$ #$}\quad⊗\ctr{$ #$}\quad⊗
\ctr{$ #$}\quad⊗\ctr{$ #$}\cr   1\cr   ⊗\dgdts\cr   ⊗⊗1\cr		       %159
\5c↓1\5⊗\ldots⊗\5c↓{k-1}\5⊗1⊗\5c↓{k+1}\5⊗\ldots⊗\5c↓n\5\cr		       %160
⊗⊗⊗⊗1\cr⊗⊗⊗⊗⊗\dgdts\cr⊗⊗⊗⊗⊗⊗1\cr}}\right),\cr				       %161
\noalign{\vskip 12pt}
U↑{-1}⊗=\left(\vcenter{\halign{\ctr{$ #$}\quad⊗\ctr{$ #$}\quad⊗\ctr{$ #$}      %162
\quad⊗\ctr{$ #$}\quad⊗\ctr{$ #$}\quad⊗
\ctr{$ #$}\quad⊗\ctr{$ #$}\cr   1\cr   ⊗\dgdts\cr   ⊗⊗1\cr		       %163
-c↓1⊗\ldots⊗-c↓{k-1}⊗1⊗-c↓{k+1}⊗\ldots⊗-c↓n\cr				       %164
⊗⊗⊗⊗1\cr⊗⊗⊗⊗⊗\dgdts\cr⊗⊗⊗⊗⊗⊗1\cr}}\right).\cr}\eqno(25)$$ 		       %165
This ends the test data, fortunately T\hskip-1pt\lower1.94pt\hjust{E}\hskip-1pt
X is working fine.\par\vfill\eject					       %166